package leetcode.D200.T130;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-18 22:44:15 星期五
 */
public class Solution {

    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        int root = m * n;
        int[] uf = initUF(root + 1);
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                if (board[i][j] == 'X')
                    continue;
                int index = i * n + j;
                if (i == 0 || i == m-1 || j == 0 || j == n-1)
                    unionFather(uf, index, root);
                else {
                    for (int k=0; k<4; ++k) {
                        int newx = i + dx[k], newy = j + dy[k];
                        if (newx >= 0 && newx < m && newy >= 0 && newy < n && board[newx][newy] == 'O')
                            unionFather(uf, index, newx * n + newy);
                    }
                }
            }
        }
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                if (board[i][j] == 'X' || i == 0 || i == m-1 || j == 0 || j == n-1)
                    continue;
                if (!isConnected(uf, root, i * n + j))
                    board[i][j] = 'X';
            }
        }
    }

    private int[] initUF(int n) {
        int[] uf = new int[n];
        for (int i=0; i<n; ++i)
            uf[i] = i;
        return uf;
    }

    private int getFather(int[] uf, int a) {
        if (a == uf[a])
            return a;
        int fa = getFather(uf, uf[a]);
        uf[a] = fa;
        return fa;
    }

    private void unionFather(int[] uf, int a, int b) {
        int fa = getFather(uf, a), fb = getFather(uf, b);
        uf[fa] = fb;
    }

    private boolean isConnected(int[] uf, int a, int b) {
        return getFather(uf, a) == getFather(uf, b);
    }
}
